package com.shuang.dp6;

class Solution {
    //动态规划
    public int integerBreak(int n) {
        //dp[i]表示 拆分i 得到的最大乘积
        int[] dp = new int[n + 1];

        //递归公式 j从1开始遍历 dp[i] 可以拆分成两个数时乘积为 j*(i-j) 三个及以上时为j*dp[i-j] dp[i]为其中的最大值

        //初始化dp dp[0] dp[1] 没有意义 题目n也是从2开始的直接初始化dp[2]即可
        dp[2] = 1;

        //遍历顺序 从前向后
        for (int i = 3; i <= n; i++){
            for (int j = 1; j < i; j++){
                //dp[i]为乘积最大值
                //j<i部分可以优化 变成j<=i/2 因为一个数拆分完 乘积最大值应该是尽可能相近的数的乘积 再往后只会又变小了
                //也可以是j <= i-j 前一半就已经把所有可能都涵盖了 后面的只是重复了
            // for (int j = 1; j <= i/2; j++){
            // for (int j = 1; j <= i - j; j++){


                dp[i] = Math.max(Math.max(j * (i - j), j * dp[i - j]), dp[i]);
            }
        }

        return dp[n];
    }
}